1303. Ультрабыстрая сортировка

В этой задаче Вам следует проанализировать работу конкретного алгоритма сортировки. Алгоритм обрабатывает последовательность из n различных целых чисел, меняя местами соседние элементы до тех пор пока все числа не будут находиться в возрастающем порядке. Например, для последовательности

9 1 0 5 4

результатом ультрабыстрой сортировки будет

0 1 4 5 9

Вам необходимо установить наименьшее количество перестановок соседних элементов, необходимое для расположения всех элементов последовательности в возрастающем порядке.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит длину входной последовательности n (n ≤ 500,000). Каждая из следующих n строк содержит одно целое число a_i (0 ≤ a_i ≤ 999999999) - i-ый элемент последовательности. Последний тест содержит n = 0 и не обрабатывается.

Выход. Для каждой входной последовательности в отдельной строке вывести целое число op – наименьшее количество перестановок соседних элементов, необходимое для сортировки элементов последовательности.

Пример входа	Пример выхода
5 9 1 0 5 4 3 1 2 3 0	6 0

РЕШЕНИЕ

структуры данных - дерево Фенвика

Анализ алгоритма

Входная последовательность содержит разные числа – от больших до малых. В общем случае она могла бы содержать и отрицательные числа. Совершим отображение n входных чисел во множество [0, …, n – 1] таким образом, чтобы результирующий массив содержал такое же число инверсий, как и исходный. Заменим каждое число a_i его индексом в отсортированном массиве (индексы начинаются с нуля). Например {99, 3, 10⁶, 16} можно отобразить в {2, 0, 3, 1}. Действительно, пусть а = {99, 3, 10⁶, 16}, b = {3, 16, 99, 10⁶} – отсортированный массив. Тогда число 99 в массиве b имеет позицию 2, число 3 в массиве b имеет позицию 0, число 10⁶ в массиве b имеет позицию 3, а число 16 в массиве b имеет позицию 1.

Задача свелась к подсчету количества инверсий в массиве, являющемся перестановкой чисел от 0 до n – 1 (отметим, что по условию задачи все числа входного массива разные). Будем двигаться по массиву из конца в начало, поддерживая дерево Фенвика по массиву b, которое изначально пусто (то есть заполнено нулями). Для каждого значения a_i сумма b₀ + b₁ + … + b_i равна количеству элементов справа от него в массиве а, с которыми a_i образует инверсию. После подсчета указанного числа инверсий увеличим b[a[i]] на 1. Таким образом, при поступлении числа a_i в массиве b единицы будут находиться лишь в тех в ячейках, индексы которых равны уже обработанным числам из массива а (индексы и числа в обновленном массиве а принимают значения от 0 до n – 1).

Пример

Входная последовательность а имеет вид:

Пять чисел отобразим во множество [0, …, 4]. Новое состояние массива а:

Количество инверсий в первой и второй последовательности одинаково. Количество инверсий, которое образует a_i с числами правее его, равно b₀ + b₁ + … + b_i. После подсчета указанного числа инверсий увеличиваем b[a[i]] на единицу.

Из массива а обработаны числа 2, 3 и 0. В ячейках с этими индексами в массиве b стоят единицы.

Общее количество инверсий равно 1 + 1 + 4 = 6.

Реализация алгоритма

Объявим рабочие массивы a и b. Работу дерева Фенвика моделируем в массиве Fenwick.

#define MAX 500001

int a[MAX], b[MAX], Fenwick[MAX];

Основная часть программы. Для каждого теста читаем входную последовательность чисел a. В переменной swaps подсчитываем количество инверсий.

while(scanf("%d",&n), n)

{

memset(Fenwick,0,sizeof(Fenwick));

for(swaps = i = 0; i < n; i++) scanf("%d",&a[i]);

Скопируем входной массив a в b и отсортируем его.

memcpy(b,a,sizeof(a));

sort(b,b+n);

Совершим отображение чисел входного массива а во множество [0, …, n – 1]. Заменяем каждое a_i его индексом в отсортированном массиве.

for(i = 0; i < n; i++)

{

pos = lower_bound(b,b+n,a[i]) - b;

a[i] = pos;

}

Для каждого значения a_i подсчитываем количество инверсий, которое оно образует со стоящими справа от него элементами в массиве a. Увеличиваем b[a[i]] на единицу.

for(i = n - 1; i >= 0; i--)

{

swaps += sum(a[i]);

update(a[i],1);

}

Выводим количество инверсий.

printf("%lld\n",swaps);

}